public class SingleLinkedList {
        public ListNode head;
        //头插法
        public void addFirst(int data) {
            ListNode listNode = new ListNode(data);
            listNode.next = head;
            head = listNode;
        }
        //尾插法
        public void addLast(int data) {
            ListNode listNode = new ListNode(data);
            if (head == null) {
                head = listNode;
                return;
            }
            ListNode cur = head;
            while (cur.next != null) {
                cur =cur.next;
            }
            cur.next = listNode;

        }

        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data) {
            try {
                checkIndex(index);
            }catch (indexNotLegalException e) {
                e.printStackTrace();
            }
            if (index == 0) {
                addFirst(data);
                return;
            }
            if (index == size()) {
                addLast(data);
                return;
            }
            ListNode listNode = new ListNode(data);
            ListNode cur = head;
            for (int i = 0; i < index - 1; i++) {
                cur = cur.next;
            }
            listNode.next = cur.next;
            cur.next = listNode;

        }
        private void checkIndex(int index) throws indexNotLegalException{
            if (index < 0 || index > size()) {
                throw new indexNotLegalException("index不合法");
            }
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key) {
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key) {
            ListNode cur = head;
            if (head.val == key) {
                head = head.next;
                return;
            }
            while (cur.next != null) {
                if (cur.next.val == key) {
                    cur.next = cur.next.next;
                    return;
                }
                cur = cur.next;
            }

        }
        //删除所有值为key的节点
        public void removeAllKey(int key) {
            if (head == null) {
                return;
            }
            ListNode pre = head;
            ListNode cur = head.next;
            while (cur != null) {
                if (cur.val == key) {
                    pre.next = cur.next;
                } else {
                    pre = pre.next;
                }
                cur = cur.next;
            }
            if (head.val == key) {
                head = head.next;
            }
        }
        //得到单链表的长度
        public int size() {
            int count = 0;
            ListNode cur = head;
            while (cur != null) {
                cur = cur.next;
                count++;
            }
            return count;
        }
        public void display() {
            ListNode cur = head;
            if (head == null) {
                System.out.println();
                return;
            }
            while (cur.next != null) {
                System.out.print(cur.val+"->");
                cur = cur.next;
            }
            System.out.print(cur.val);
        }
        public void clear() {
            head = null;
        }

}
class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}
